package algorithm_primary.studyMySelf.初级算法.双指针;

/**
 * @author mengHao.heng
 * @date 2023/5/23 9:35
 * @description 一一盛最多水的容器
 * 11. 盛最多水的容器
 * 提示
 * 中等
 * 4.3K
 * 相关企业
 * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 * <p>
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * <p>
 * 返回容器可以储存的最大水量。
 * <p>
 * 说明：你不能倾斜容器。
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * <p>
 * <p>
 * 输入：height = [1,1]
 * 输出：1
 */
public class 一一盛最多水的容器 {

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(height));
    }

    private static int maxArea(int[] height) {
        //[1,8,6,2,5,4,8,3,7]
        int l = 0, r = height.length - 1, min = 0;
        int maxH= 0;
        while (r > l) {
            // 如果左边的高度低于右边的高度  那么说明需要乘的高是左边的  因为有一个容器是的高度是根据两边最低的为标准
            maxH = Math.min(height[l], height[r]);
            min = Math.max(min,maxH * (r - l));
            while (height[l] <= maxH && r > l) {
                l++;
            }
            while ( height[r]<= maxH && r > l) {
                r--;
            }
        }
        return min;
    }
}

/**
 * 分析
 * <p>
 * 我们先从题目中的示例开始，一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。
 * <p>
 * 题目中的示例为：
 * <p>
 * [1, 8, 6, 2, 5, 4, 8, 3, 7]
 * ^                       ^
 * 在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 min⁡(1,7)∗8=8\min(1, 7) * 8 = 8min(1,7)∗8=8。
 * <p>
 * 此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由
 * <p>
 * 两个指针指向的数字中较小值∗指针之间的距离 两个指针指向的数字中较小值 * 指针之间的距离
 * 两个指针指向的数字中较小值∗指针之间的距离
 * 决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
 * <p>
 * 有读者可能会产生疑问：我们可不可以同时移动两个指针？ 先别急，我们先假设 总是移动数字较小的那个指针 的思路是正确的，在走完流程之后，我们再去进行证明。
 * <p>
 * 所以，我们将左指针向右移动：
 * <p>
 * [1, 8, 6, 2, 5, 4, 8, 3, 7]
 * ^                    ^
 * 此时可以容纳的水量为 min⁡(8,7)∗7=49\min(8, 7) * 7 = 49min(8,7)∗7=49。由于右指针对应的数字较小，我们移动右指针：
 * <p>
 * [1, 8, 6, 2, 5, 4, 8, 3, 7]
 * ^                 ^
 * 此时可以容纳的水量为 min⁡(8,3)∗6=18\min(8, 3) * 6 = 18min(8,3)∗6=18。由于右指针对应的数字较小，我们移动右指针：
 * <p>
 * [1, 8, 6, 2, 5, 4, 8, 3, 7]
 * ^              ^
 * 此时可以容纳的水量为 min⁡(8,8)∗5=40\min(8, 8) * 5 = 40min(8,8)∗5=40。两指针对应的数字相同，我们可以任意移动一个，例如左指针：
 * <p>
 * [1, 8, 6, 2, 5, 4, 8, 3, 7]
 * ^           ^
 * 此时可以容纳的水量为 min⁡(6,8)∗4=24\min(6, 8) * 4 = 24min(6,8)∗4=24。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：min⁡(2,8)∗3=6\min(2, 8) * 3 = 6min(2,8)∗3=6，min⁡(5,8)∗2=10\min(5, 8) * 2 = 10min(5,8)∗2=10，min⁡(4,8)∗1=4\min(4, 8) * 1 = 4min(4,8)∗1=4。
 * <p>
 * 在我们移动指针的过程中，计算到的最多可以容纳的数量为 494949，即为最终的答案。
 * <p>
 * 作者：力扣官方题解
 * 链接：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
